Algorithm CH15 DP
algorithm CH15 DP
Ex. Rod cutting
input:
- n length of rod
price of rod with diff. length
output:- max price
Assume lenght of rod is n, how many method to cut rod?
Ans.
to prevent exponential complecity, using DP
want to sort q. using DP
need
- optimal substructure
- 可以獲得子問題的最佳解
簡化rod cutting
- 可以靠最左邊的那一刀
for 1<=i<=n
method
- Top-down
- recursive
- 導致重複計算
- T(n) =
- DP bottom-up
- 把算過的子問題 放在表裡->不用重複計算
- T(n) =
Subproblem graph
each vertex is a subproblem
exist arc between x and y, means wants to solve x need to solve y first
印出切刀的順序
用一個新的表紀錄對於長度為n的rod
最左邊的刀是哪裡
所以下一刀就是
now_length - s[i] = new_length
s[new_length]
Ex2. LCS
保持相對順序挑出字元,如果兩個sequence抽出的字元一樣
- common subsequence
- 不一定要連續
- LCS
- 越長越好
暴力法
使用DP需要符合以下兩個特性
- optimal substructure
- bottom-up
- overlapping subproblem
- using chart to record ans.
by using optimal structure
- theorem, 可以由最後一個字元來判斷
- 如下圖
定義遞迴關係式
創建c, b table
- c用於找LCS
- b用於紀錄最佳的結果
- pseudo code
- row major
- row major
Ex.
印出LCS
- 根據b table
optimal binary search tree
Actual cost = # of items examined
- For key
, cost = depthT( ) + 1, where depthT( ) = depth of in BST T.
search cost
- E(x)
Ex.
- search cost
- 越小的cost,樹就越好
- 越小的cost,樹就越好
Observation
- Optimal BST might not have smallest height.
- Optimal BST might not have highest-probability key at root.
force method
- Construct each n-node BST.
- For each, put in keys.
- Then compute expected search cost.
- But there are
different BSTs with n nodes.
optimal substructure
divide to 2 subtree
- let r be root of two subtree
- 人人有機會 個個沒把握
- if j=i-1, tree is empty
recursive sol.
pseudo code
Algorithm CH15 DP
https://z-hwa.github.io/webHome/[object Object]/Algorithm/Algorithm-CH15-DP/